package net.tree;

public class BTree {
    TreeNode<Integer> root;
    //二叉排序树： 唯一
    //中序：有序
    //效率高
    public void add(Integer value){
        //根节点
        if (root == null){
            root = new TreeNode<>(value);
            return;
        }
        //插入？先比较（每次都是从根进行比较），再插入（一定是没有孩子才能插入）

        //每次都是从根进行比较
        TreeNode<Integer> currentNode = root;
        //比较
        while (true){
            if (value<currentNode.data){//向左走
                if (currentNode.Left == null){//插入
                    currentNode.Left = new TreeNode<>(value);
                    return;
                }
                currentNode = currentNode.Left;
            }else if (value > currentNode.data){
                if (currentNode.right == null){
                    currentNode.right = new TreeNode<>(value);
                    return;
                }
                currentNode = currentNode.Left;
            }else {
                return;
            }
        }
    }
    /**
     * 查找
     * */
    public boolean serach(int key) {
        TreeNode<Integer> currentNode = root;
        while (true) {
            if (currentNode == null) {
                return false;
            }
            if (currentNode.data == key) {
                return true;
            }
            if (key < currentNode.data) {
                currentNode = currentNode.left;
            } else {
                if (key > currentNode.data) {
                    currentNode = currentNode.right;
                }
            }
        }
    }
    /**
     * 另一种查找（递归）
     * */
    public boolean find(TreeNode<Integer> node,int key){
        if (node==null){
            return false;
        }
        if (node.data==key){
            return true;
        }
        if (key>node.data){
            return find(node.right,key);
        }else {
            return find(node.left,key);
        }

    }
        //中
        public void midOrder (TreeNode node){
            if (node != null) {

                //左
                midOrder(node.Left);
                //根
                System.out.println(node.data);
                //右
                midOrder(node.right);
            }
        }
    }

